#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/29 11:17
# ===========================================
#       题目名称： 45. 跳跃游戏 II
#       题目地址： https://leetcode.cn/problems/jump-game-ii/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
from typing import List


class Solution:
    def jump(self, nums: List[int]) -> int:
        jump = 0  # 初始跳跃次数
        start, end = 0, 1  # 定义起始位置
        while end < len(nums):
            max_val = 0
            for cur_index in range(start, end):
                max_val = max(max_val, cur_index + nums[cur_index])
            start = end
            end = max_val + 1
            jump += 1
        return jump


if __name__ == '__main__':
    s = Solution()
    # 2
    print(s.jump(nums=[2, 3, 1, 1, 4]))
    # 2
    print(s.jump(nums=[2, 3, 0, 1, 4]))
